A variety of approaches to the communication of data in network-type communications are implemented to suit various needs. Many networks are made up of a multitude of interconnected links, often connecting sub-networks within a larger network. Data can be routed across connected nodes in various points in the network in traveling from a data source to a data destination. Each leg of the path via which data travels from the source to destination is often referred to as a “hop,” e.g., in the context of the number of links or nodes that data traverses. Where different networks are connected via routers, data can be passed from network to network by passing the data from one router to another, until the data reaches its destination (i.e., to a network node served by a router via which the data is sent). In such a router-based approach, each time data is accepted and routed by a particular router corresponding to a leg, or hop, in the data's journey to its destination. In general, connected networks of these or other types can be referred to as interconnection networks.
Interconnection networks are widely used today in a variety of applications such as those involving switch and router fabrics, processor-memory interconnect and I/O interconnect approaches. See, e.g., W. J. Daily, P. P. Carvey, and L. R. Dennison, The Avici terabit switch/router, Proc. of Hot Interconnects, pages 41-50, August 1998; S. L. Scott and G. M. Thorson, The Cray T3E network: Adaptive routing in a high performance 3D torus, Proc. of Hot Interconnects, pages 147-156, August 1996; and G. Pfister, High Performance Mass Storage and Parallel I/O, Chapter 42, pages 617-632, IEEE Press and Wiley Press, 2001. Three aspects of the design of an interconnection network include the topology, the routing algorithm used, and the flow control mechanism employed. The topology is generally chosen to exploit the characteristics of the available packaging technology to meet requirements such as bandwidth, latency and scalability of the application, at a minimum cost. Once the topology of the network is fixed, so are the bounds on its performance. For instance, the topology determines the maximum throughput (in bits/s) and zero-load latency (in hops) of the network. The routing and flow-control then strive to achieve these performance bounds.
Interconnection networks can be characterized as symmetric and asymmetric topologies. Symmetric topologies, in which each node has the same degree, have been popular in the interconnection networks community. All nodes in a symmetric topology can employ the same routing algorithm, irrespective of their orientation in the network. The symmetry of the network is also helpful for solving issues related to VLSI design. The function of a routing algorithm with symmetric topologies is generally to select a path to route a packet from its source, s, to its destination, d. Routing algorithms often make route selections in a manner that exploits locality to provide low latency and high throughput on benign traffic.
Many applications benefit from the provision of high throughput on adversarial traffic patterns for interconnection networks. In an Internet router, for example, there is no backpressure on input channels so the interconnection network used for the router fabric handles any traffic pattern, even the worst-case, at the line rate or packets will be dropped. To meet their specifications, I/O networks often provide guaranteed throughput on all traffic patterns between host and disk nodes. Some multi-computer applications are characterized by random permutation traffic, wherein each node sends all messages to a single, randomly-selected node. Random permutation traffic often arises when operating on an irregular graph structure or on a regular structure that is randomly mapped to the nodes of the machine. The throughput of the network on adversarial patterns can limit performance on these applications.
Routing algorithms are often implemented to strike a balance between the conflicting goals of providing low latency on local traffic and providing high throughput on adversarial traffic. To achieve high performance on local traffic, minimal routing algorithms that choose a shortest path for each packet are often favored. A minimal route is dynamically selected at each hop, based on the congestion of outgoing channels at that hop. Minimal algorithms, however, perform poorly on worst-case traffic due to load imbalance, and adversarial traffic patterns can load some links very heavily while leaving others idle.
Other routing approaches have involved random routing, such as those implemented with Valiant's algorithm (VAL), which is a fully randomized, two-phase routing algorithm. In the first phase, packets are routed from the source to a randomly chosen intermediate node using minimal routing. The second phase routes minimally from the intermediate node to the destination. In performing optimally in the worst case on symmetric networks, the VAL approach destroys locality, resulting in relatively poor performance on local traffic.
The above and other issues have presented challenges to routing approaches and, in particular, to routing in networks such as interconnection networks.